package com.future;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Description: NC183 最长公共子数组
 *
 * @author weiruibai.vendor
 * Date: 2022/7/29 17:25
 */
public class Solution_NC183 {

    public static void main(String[] args) {
        Solution_NC183 nc183 = new Solution_NC183();
        int[] A = {1, 2, 5, 5, 7, 8};
        int[] B = {2, 5, 7, 8, 5};
        System.out.println(nc183.longestCommonSubarry(A, B));
    }

    /**
     * @param A
     * @param B
     * @return
     */
    public int longestCommonSubarry(int[] A, int[] B) {
        int ans = 0;
        int aLength = A.length;
        int bLength = B.length;
        /**
         * 计算数组每个数组出现的位置
         */
        Map<Integer, List<Integer>> bIndexMap = buildBIndexMap(B);
        for (int i = 0; i < A.length; i++) {
            int num = A[i];
            if (bIndexMap.containsKey(num)) {
                List<Integer> list = bIndexMap.get(num);
                for (int j = 0; j < list.size(); j++) {
                    int aR = i;// 数组A同一个数的起点
                    int bR = list.get(j);// 数组B同一个数的起点
                    while (aR < aLength && bR < bLength && A[aR] == B[bR]) {
                        aR++;
                        bR++;
                    }
                    ans = Math.max(ans, aR - i);
                }
            }
        }
        return ans;
    }

    /**
     * 计算数组每个数组出现的位置
     *
     * @param b
     * @return
     */
    private Map<Integer, List<Integer>> buildBIndexMap(int[] b) {
        Map<Integer, List<Integer>> bIndexMap = new HashMap<>();
        for (int i = 0; i < b.length; i++) {
            List<Integer> orDefault = bIndexMap.getOrDefault(b[i], new ArrayList<>());
            orDefault.add(i);
            bIndexMap.put(b[i], orDefault);
        }
        return bIndexMap;
    }

}
